package sortArray;
/*
 * @lc app=leetcode.cn id=912 lang=java
 *
 * [912] 排序数组
 */

import java.util.Random;

// @lc code=start
class Quick {
  public int[] sortArray(int[] nums) {
    quick(nums, 0, nums.length - 1);
    return nums;
  }

  void quick(int[] nums, int l, int r) {
    if (l >= r) {
      return;
    }
    int pos = partition(nums, l, r);
    quick(nums, l, pos - 1);
    quick(nums, pos + 1, r);
  }

  int partition(int[] nums, int l, int r) {
    int pivotIdx = new Random().nextInt(r - l + 1) + l;
    swap(nums, pivotIdx, r);
    int pivot = nums[r];
    int leftIdx = l;
    for (int i = l; i <= r - 1; i++) {
      if (nums[i] < pivot) {
        swap(nums, leftIdx, i);
        leftIdx++;
      }
    }
    swap(nums, leftIdx, r);
    return leftIdx;
  }

  void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}
// @lc code=end
